LCA Tarjan离线算法

算法

相关的介绍

描述

LCA问题，即Least Common Ancestors,最近公共祖先问题，给定一棵树T再给出一些查询LCA（u,v）（当查询量较大的时候），每次查询的都是u和v的祖先，并且让所查询的点的深度尽可能的深。

解决LCA问题的方法

线段树，Tarjan，RMQ，倍增

LCA问题的形式

给定一棵树，并给出若干个查询每个查询要求指定节点u和v的最近公共祖先

解决思路

·在线算法：对每个查询进行处理给出答案
·离线算法：进行与处理之后对于每一个查询给出答案

算法思路

Tarjan离线算法是基于DFS和并查集的一种算法，算法从根节点开始每次递归搜索所有的子树，再处理当前根节点相关的所有查询。
每当搜索到点n的时候，就创建一个关于该点的集合，这个集合的先祖就是n自己，接下来递归搜素n的所有的子树，每搜索完一个子树的时候就把该子树的集合与n集合相连接起来，并且把这个合并之后的集合的先祖设为n，因为这棵子树内的已经查询完毕了，n的其他子树节点跟这颗的LCA都是一样的，都为当前节点x。所有的子树处理完毕之后处理当前根节点n的查询。遍历n的所有查询，如果所查询的另外一个点已经遍历过了，那么n和v的LCA即为v所在的集合的祖先。

总结

从最底层开始往上遍历合并子树，直到两个查询的节点都已经被标记过了，那么当前位置所在的根即为我们所要寻找的LCA（u,v）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
typedef int mytype;
const int NV=40005;
const int NE=NV;
const int NQ=10005;
mytype dis[NV],ans[NV];
int vis[NV],he[NV],hq[NV],ecnt,qcnt;
struct edge
{
    int v,next;
    mytype l;
} E[2*NE];
struct quer
{
    int v,next,i;
} q[2*NQ];
void adde(int u,int v,mytype l)
{
    E[++ecnt].v=v;
    E[ecnt].l=l;
    E[ecnt].next=he[u];
    he[u]=ecnt;
}
void addq(int u,int v,int i)
{
    q[++qcnt].v=v;
    q[qcnt].i=i;
    q[qcnt].next=hq[u];
    hq[u]=qcnt;
}
int fa[NV],rk[NV];
void init(int n,int m)
{
    ecnt=0;
    qcnt=0;
    memset(vis,0,sizeof(vis));
    memset(rk,0,sizeof(rk));
    memset(he,-1,sizeof(he));
    memset(hq,-1,sizeof(hq));
    for (int i=1; i<=m; i++)
    {
        int u,v;
        mytype l;
        scanf("%d%d%d",&u,&v,&l);
        adde(u,v,l);
        adde(v,u,l);
    }
}
int finds(int x)
{
    int k,j,r;
    r=x;
    while(r!=fa[r])
        r=fa[r];
    k=x;
    while(k!=r)
    {
        j=fa[k];
        fa[k]=r;
        k=j;
    }
    return r;
}
void tarjan(int u,mytype d)
{
    dis[u]=d;
    fa[u]=u;
    vis[u]=1;
    for (int i=he[u]; i!=-1; i=E[i].next)
        if (!vis[E[i].v])
            tarjan(E[i].v,d+E[i].l),fa[E[i].v]=u;
    for (int i=hq[u]; i!=-1; i=q[i].next)
        if (vis[q[i].v])
            ans[q[i].i]=dis[u]+dis[q[i].v]-2*dis[finds(q[i].v)];
}
void solve(int n,int m)
{
    init(n,m);
    int k;
    scanf("%d",&k);
    for (int i=1; i<=k; i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        addq(u,v,i);
        addq(v,u,i);
    }
    tarjan(1,0);
    for (int i=1; i<=k; i++)
        printf("%d\n",ans[i]);
}

友情链接

http://noalgo.info/476.html
https://github.com/fz568573448/ACM-ICPC-Template/blob/master/%E6%A8%A1%E6%9D%BF/8_%E5%9B%BE%E8%AE%BA/13_LCA%E7%9A%84tarjan%E7%A6%BB%E7%BA%BF%E7%AE%97%E6%B3%95.cpp